package simple;

/**
 * @author cmqzyd0700@163.com
 * @version 1.0
 * @since 2020/3/15 22:05
 */
public class No14_最长公共前缀 {
    public static void main(String[] args) {
        //略烧脑,慢慢玩
        Solution14 solution14 = new Solution14();
        //String[] strs = new String[]{"flag","flame","flaw","flue",
        //        "flau","flawq","fcacc","fbcb"
        //};
        String[] strs = new String[]{"a", "cc", "aad"};

        String result = solution14.longestCommonPrefix(strs);
        System.out.println();
    }
}

class Solution14 {
    public String longestCommonPrefix(String[] strs) {
        //中度烧脑,慢慢理解,我先休息休息,刚不住了,大家自便,喜欢关注一下
        //每天带你烧脑,拜拜!!!!明天继续!!!
        //二分查找法
        if (strs == null || strs.length == 0) {
            return "";
        }
        int minLength = Integer.MAX_VALUE;
        for (String str : strs) {
            minLength = Math.min(minLength, str.length());
        }

        int green = 0;
        int red = minLength - 1;
        while (green <= red) {
            int mid = (green + red) >>> 1;
            if (isPremix(strs, mid)) {
                green = mid + 1;
            } else {
                red = mid - 1;
            }
        }
        //规避-2147483648这玩意
        if (red < 0) {
            return "";
        }
        return strs[0].substring(0, ((green + red) >>> 1) + 1);
    }

    //获取(0,len + 1) 长度的字符串是不是数组前缀
    public boolean isPremix(String[] strs, int len) {
        String base = strs[0].substring(0, len + 1);
        for (int i = 0; i < strs.length; i++) {
            if (!strs[i].startsWith(base)) {
                return false;
            }
        }
        return true;
    }

}

    //public String longestCommonPrefix(String[] strs) {
    //    //一路递归到底法
    //    if (strs == null || strs.length == 0) {
    //        return "";
    //    }
    //    String 一路递归 = 一路递归(strs, 0, strs.length - 1);
    //    return 一路递归;
    //}
    //
    //
    ////green到red之间求最大公共前缀
    //public String 一路递归(String[] strs, int green, int red) {
    //    if (green == red) {
    //        return strs[green];
    //    }
    //    int mid = (green + red) >>> 1;
    //    String leftStr = 一路递归(strs, green, mid);
    //    String rightStr = 一路递归(strs, mid + 1, red);
    //    String result = getJ(leftStr, rightStr);
    //    return result;
    //}
    //
    ////求left和right的公共前缀
    //public String getJ(String left, String right) {
    //    //"flag","flage"
    //    int minLength = Math.min(left.length(), right.length());
    //    for (int i = 0; i < minLength; i++) {
    //        if (left.charAt(i) != right.charAt(i)) {
    //            return left.substring(0, i);
    //        }
    //    }
    //    return left.substring(0, minLength);
    //}

    //public String longestCommonPrefix(String[] strs) {
    //    if (strs == null || strs.length == 0) {
    //        return "";
    //    }
    //    //扫描法,一个一个来
    //    String base = strs[0];
    //    for (int i = 0; i < base.length(); i++) {
    //        char c = base.charAt(i); // 'f'
    //        for (int j = 1; j < strs.length; j++) {
    //            if (i == strs[j].length() || strs[j].charAt(i) != c) {
    //                return strs[0].substring(0, i);
    //            }
    //        }
    //    }
    //    return base;
    //}


    //public String longestCommonPrefix(String[] strs) {
    //    if (strs.length == 0) {
    //        return "";
    //    }
    //    //暴力法
    //    int minLength = Integer.MAX_VALUE;
    //    String result = "";
    //    String checkStr = "";
    //    for (String str : strs) {
    //        minLength = Math.min(minLength, str.length());
    //    }
    //    //随便一个字符串
    //    for (String str : strs) {
    //        if (str.length() == minLength) {
    //            checkStr = str;
    //            break;
    //        }
    //    }
    //
    //    for (int i = minLength; i >= 1; i--) {
    //        boolean flag = true;
    //        String checkKey = checkStr.substring(0, i);
    //        for (String str : strs) {
    //            String check = str.substring(0, i);
    //            if (!check.equals(checkKey)) {
    //                flag = false;
    //                break;
    //            }
    //        }
    //        if (flag) {
    //            result = checkKey;
    //            break;
    //        }
    //    }
    //    return result;
    //
    //
    //}